这题在 AtCoder 的评分是 3266,感觉肯定是黑题,但是咋就通过了呢(
题意翻译的不够清楚,重新解释一遍:(做这题的时候看了好久也没看懂,然后就去原题看英文题面了)
定义 为:对于一个字符串 ,每次将它最左边的字符放置到字符串末尾生成的字符串集合中,字典序最小的字符串。例如:对于 为 bcbca 的情况, 即为 babca、abcab、bcaba、cabab、abcbc 中最小的那个,即 abcbc。
你需要构造一个字符串 ,共包含 个字符 a、 个字符 b 和 个字符 c,使得 尽可能大,输出这个 。
思路:
要使得 尽可能大,每次循环求一遍显然不现实,最好构造出一种 使得它本身就是 (即:)。
那么怎么构造呢?
我们可以使用 multiset 来记录所有供选择的字符串,每次合并两个字符串,直到集合中只剩一个为止。合并的方法是取最小的字符串 与最大的字符串 ,将 拼接到 后面,重新加入集合。
这种情况下,这个前缀因为是最小的,所以从任何其它地方开头取字符串均不会更小,保证了 。
代码:
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define loop while(true)
#define rep(x,y,z) for(int (x)=(y);(x)<=(z);(x)++)
#define per(x,y,z) for(int (x)=(y);(x)>=(z);(x)--)
#define fil(x,y) memset((x), (y), sizeof(x))
using namespace std;
typedef long long ll;
int x, y, z; multiset<string> qwq;
int main() {
scanf("%d%d%d", &x, &y, &z);
rep(i, 1, x) qwq.insert("a");
rep(i, 1, y) qwq.insert("b");
rep(i, 1, z) qwq.insert("c");
while(qwq.size() ^ 1) {
multiset<string>::iterator it1 = qwq.begin();
multiset<string>::reverse_iterator it2 = qwq.rbegin();
string a = (*it1), b = (*it2), _ = a + b;
qwq.erase(qwq.lower_bound(a)); qwq.erase(qwq.lower_bound(b));
qwq.insert(_);
}
multiset<string>::iterator it = qwq.begin();
cout<<(*it)<<endl;
return 0;
}
(顺带一提,无意中还抢到了 R42600000,虽然有个地方错了 QAQAQ)